package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	slow := head
	fast := head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	mid := slow.Next
	slow.Next = nil

	head1 := sortList(head)
	head2 := sortList(mid)

	return mergeList(head1, head2)
}

func mergeList(head1 *ListNode, head2 *ListNode) *ListNode {
	n := &ListNode{}
	result := n
	for head1 != nil && head2 != nil {
		if head1.Val < head2.Val {
			n.Next = head1
			head1 = head1.Next
		} else {
			n.Next = head2
			head2 = head2.Next
		}
		n = n.Next
	}
	if head1 != nil {
		n.Next = head1
	}
	if head2 != nil {
		n.Next = head2
	}
	return result.Next
}

func main() {
	n1 := &ListNode{Val: 1}
	n2 := &ListNode{Val: 2}
	n3 := &ListNode{Val: 3}
	n4 := &ListNode{Val: 4}
	n5 := &ListNode{Val: 5}

	n1.Next = n3
	n3.Next = n5
	n5.Next = n2
	n2.Next = n4
	sortList(n1)
	println(n1)
}
